import java.util.Arrays;

/**
 * 1589. 所有排列中的最大和
 * https://leetcode-cn.com/problems/maximum-sum-obtained-of-any-permutation/
 */
public class Solutions_1589 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int[][] requests = {{1, 3}, {0, 1}};  // output: 19
//        一个总和更大的排列为 {3, 5, 4, 2, 1}，并有如下结果：
//        requests{0} -> nums{1} + nums{2} + nums{3} = 5 + 4 + 2 = 11
//        requests{1} -> nums{0} + nums{1} = 3 + 5  = 8

//        int[] nums = {1, 2, 3, 4, 5, 6};
//        int[][] requests = {{0, 1}};  // output: 11
//        解释：一个总和最大的排列为 {6, 5, 4, 3, 2, 1}，查询和为 {11}。

//        int[] nums = {1, 2, 3, 4, 5, 10};
//        int[][] requests = {{0, 2}, {1, 3}, {1, 1}};  // output: 47
//        解释：一个和最大的排列为 {4, 10, 5, 3, 2, 1}，查询结果分别为 {19, 18, 10}。

        int result = maxSumRangeQuery(nums, requests);
        System.out.println(result);
    }

    /**
     * 解题思路：（贪心思想，差分数组的应用）
     * 将较大的数，安排在查询次数最多的索引上
     */
    public static int maxSumRangeQuery(int[] nums, int[][] requests) {
        int mod = 1_000_000_007;
        int len = nums.length;

        // counts[1] = 3，表示 requests 中，查询索引 1 的次数是 3 次
        int[] counts = new int[len + 1];
        int start = 0, end = 0;
        // 为 counts 数组计数（类似于 start 车站上车，end + 1 车站下车，[start, end] 区间段，则一起在车上）
        for (int[] req : requests) {
            start = req[0];
            end = req[1];
            counts[start] ++;
            counts[end + 1] --;
        }
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }
        // 排序后，倒序遍历，即知道最大值
        Arrays.sort(counts);
        Arrays.sort(nums);
        long res = 0L;
        for (int i = counts.length - 1; i >= 0 && counts[i] > 0; i--) {
            // 较大的数，查询 counts[i] 次
            // 转换成 long 型时，不需要加括号，因为括号里的两个 int 值，如果计算结果已经溢出了，那么再转换成 long 也无用
//            res += (long) (nums[i - 1] * counts[i]);
            res += (long) nums[i - 1] * counts[i];
        }
        return (int) (res % mod);
    }
}
